import java.util.ArrayList;
import java.util.List;

public class Solution54 {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list=new ArrayList<>();
        int m=matrix.length,n=matrix[0].length;
        int[] dx=new int[]{0,1,0,-1};
        int[] dy=new int[]{1,0,-1,0};
        int d=0,cx=0,cy=-1;
        for (int i=1;i<=m*n;i++){
            while (!valid(cx+dx[d],cy+dy[d],m,n) || matrix[cx+dx[d]][cy+dy[d]]==-200){
                d=(d+1)%4;
            }
            cx=cx+dx[d];
            cy=cy+dy[d];
            list.add(matrix[cx][cy]);
            matrix[cx][cy]=-200;
        }
        return list;
    }

    boolean valid(int x,int y,int m,int n){
        return x>=0 && x<m && y>=0 && y<n;
    }

    public static void main(String[] args) {
        System.out.println(new Solution54().spiralOrder(new int[][]{{1,2,3,4},{5,6,7,8},{9,10,11,12}}));
    }
}
